package com.togo.algorithm.easy.search;

/**
 * @Author taiyn
 * @Description
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [0,1,3]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *  
 *
 * 限制：
 *
 * 1 <= 数组长度 <= 10000
 *
 * @Date 2:23 PM 2023/5/25
 **/
public class Offer53_2 {

    public int missingNumber(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            if(i != nums[i]) return i;
        }

        return nums.length;
    }

    public int missingNumberByBinary(int[] nums) {
        int left = 0, right = nums.length -1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(mid == nums[mid]) left = mid + 1;
            else right = mid - 1;
        }

        return left;
    }
}
